#include "DynamicArray.h"

namespace DARRAY
{
DynamicArray::DynamicArray() : size(0), capacity(10)
{
    array = new ElemetType[capacity];
    Free = nullptr;
}

DynamicArray::DynamicArray(const DynamicArray &a)
{
    std::cout<<"deep copy"<<std::endl;
    this->size = a.size;
    this->capacity = a.capacity;
    this->array = new ElemetType[capacity];
    for (size_t i = 0; i < size; i++)
    {
        this->array[i] = a.array[i];
    }
}

DynamicArray &DynamicArray::operator=(const DynamicArray &a)
{
    //删除防止塞不进去
    delete[] array;
    this->size = a.size;
    this->capacity = a.capacity;
    this->array = new ElemetType[capacity];
    for (int i = 0; i < size; i++)
    {
        this->array[i] = a.array[i];
    }
    return *this;
}



DynamicArray::~DynamicArray()
{

    if (Free)
    {
        for (size_t i = 0; i < size; i++)
        {

            Free(array[i]);
        }
    }
    delete[] array;
}

// 复杂度：不扩容O(1)  扩容O(N)
void DynamicArray::InsertTail(const ElemetType &element)
{
    if (size == capacity)
    {
        capacity *= 2;
        ReSize(capacity);
    }

    array[size] = element;
    size++;
}

// 复杂度O(n)
void DynamicArray::InsertHead(const ElemetType &element)
{
    if (size == capacity)
    {
        capacity *= 2;
        ReSize(capacity);
    }
    for (size_t i = size; i > 0; i--)
    {
        array[i] = array[i - 1];
    }
    array[0] = element;
    size++;
}

void DynamicArray::InsertByIndex(const ElemetType &element, size_t index)
{
    if (index > size)
    {
        std::cout << "位置非法" << std::endl;
        return;
    }
    if (size == capacity)
    {
        capacity *= 2;
        ReSize(capacity);
    }
    for (size_t i = size; i > index; i--)
    {
        array[i] = array[i - 1];
    }
    array[index] = element;
    size++;
}

// 复杂度O(n)
void DynamicArray::RemoveByIndex(size_t index)
{
    if (index >= size)
    {
        std::cout << "位置非法" << std::endl;
    }

    for (size_t i = index; i < size - 1; i++)
    {
        array[i] = array[i + 1];
    }
    size--;
}

// O(n^2)
void DynamicArray::RemoveByElement(const ElemetType &element)
{
    for (size_t i = 0; i < size; i++)
    {
        if (Compare(array[i], element) == 0)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

// 复杂度O(1)
ElemetType *DynamicArray::FindByIndex(size_t index)
{
    if (index >= size)
    {
        return nullptr;
    }

    return &array[index];
}

DynamicArray DynamicArray::FindByElement(const ElemetType &element)
{
    DynamicArray result;
    for (size_t i = 0; i < size; i++)
    {
        if (Compare(array[i], element) == 0)
        {
            result.InsertTail(element);
        }
    }
    return result;
}

// O(1)
void DynamicArray::UpdateByIndex(size_t index, const ElemetType &element)
{
    if (index >= size)
    {
        std::cout << "位置非法" << std::endl;
    }
    //here   not double free?
    array[index] = element;
}

// O(n)
void DynamicArray::UpdateByElement(const ElemetType &oldelement, const ElemetType &newelement)
{
    for (size_t i = 0; i < size; i++)
    {
        if (Compare(array[i], oldelement) == 0)
        {
            UpdateByIndex(i, newelement);
        }
    }
}

ElemetType &DynamicArray::operator[](int index)
{
    //here为什么？ ElemetType &result=array[index];
    return array[index];
}

// 最大深度怎么来的
//复杂度范围
// logn< h  <n
// 一般取2*logn
void DynamicArray::Sort()
{
    FastSort(0, size - 1, 0, 2 * log2(size));
}

// O(n)
void DynamicArray::Duplicate()
{
    for (size_t i = 1; i < size; i++)
    {
        if (Compare(array[i], array[i - 1]) == 0)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

// O(n) 稳定
DynamicArray DynamicArray::Merge(const DynamicArray &a)
{
    DynamicArray result;
    size_t first = 0;  // 当前数组
    size_t second = 0; // 传进来的数组
    while (first < this->size && second < a.size)
    {
        if (Compare(array[first], a.array[second]) == -1)
        {
            result.InsertTail(array[first]);
            first++;
        }
        else
        {
            result.InsertTail(a.array[second]);
            second++;
        }
    }

    while (first < this->size)
    {
        result.InsertTail(array[first]);
        first++;
    }

    while (second < a.size)
    {
        result.InsertTail(a.array[second]);
        second++;
    }

    return result;
}

DynamicArray DynamicArray::FdIntrSctn(const DynamicArray &a)
{
    DynamicArray result;
    size_t first = 0;  // 当前数组
    size_t second = 0; // 传进来的数组

    while (first < this->size && second < a.size)
    {
        if (Compare(array[first], a.array[second]) == 0)
        {
            result.InsertTail(array[first]);
            first++;
            second++;
        }
        else if (Compare(array[first], a.array[second]) == -1)
        {
            first++;
        }
        else if (Compare(array[first], a.array[second]) == 1)
        {
            second++;
        }
    }
    // result.Duplicate();
    return result;
}

DynamicArray DynamicArray::FindUnionSet(const DynamicArray &a)
{
    DynamicArray result;
    size_t first = 0;  // 当前数组
    size_t second = 0; // 传进来的数组

    while (first < this->size && second < a.size)
    {
        if (Compare(array[first], a.array[second]) == 0)
        {
            result.InsertTail(array[first]);
            first++;
            second++;
        }
        else if (Compare(array[first], a.array[second]) == -1)
        {
            result.InsertTail(array[first]);
            first++;
        }
        else if (Compare(array[first], a.array[second]) == 1)
        {
            result.InsertTail(a.array[second]);
            second++;
        }
    }

    while (first < this->size)
    {
        result.InsertTail(array[first]);
        first++;
    }

    while (second < a.size)
    {
        result.InsertTail(a.array[second]);
        second++;
    }

    // result.Duplicate();
    return result;
}

DynamicArray DynamicArray::FindDifference(const DynamicArray &a)
{
    DynamicArray result;

    size_t first = 0;  // 当前数组
    size_t second = 0; // 传进来的数组

    while (first < this->size && second < a.size)
    {
        if (Compare(array[first], a.array[second]) == 0)
        {
            first++;
            second++;
        }
        else if (Compare(array[first], a.array[second]) == -1)
        {
            result.InsertTail(array[first]);
            first++;
        }
        else if (Compare(array[first], a.array[second]) == 1)
        {
            result.InsertTail(a.array[second]);
            second++;
        }
    }

    while (first < this->size)
    {
        result.InsertTail(array[first]);
        first++;
    }

    while (second < a.size)
    {
        result.InsertTail(a.array[second]);
        second++;
    }

    return result;
}

bool DynamicArray::operator==(const DynamicArray &a)
{
    // std::cout<<"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    if (size != a.size)
    {
        return false;
    }

    size_t first = 0;  // 当前数组
    size_t second = 0; // 传进来的数组
    while (first < this->size && second < a.size)
    {
        if (Compare(array[first], a.array[second]) != 0)
        {
            return false;
        }
        first++;
        second++;
    }
    return true;
}

size_t DynamicArray::BinarySearch(const ElemetType &element)
{
    size_t left = 0;
    size_t right = size - 1;
    while (left <= right)
    {
        size_t mid = left + (right - left) / 2;
        if (Compare(array[mid], element) == 0)
        {
            return mid;
        }
        else if (Compare(array[mid], element) == 1)
        {
            if (mid == 0)
            {
                return ULONG_MAX;
            }
            else
            {
                right = mid - 1;
            }
        }
        else
        {
            left = mid + 1;
        }
    }
    return ULLONG_MAX;
}

bool DynamicArray::Contains(const DynamicArray &a)
{
    // DynamicArray s=FdIntrSctn(a);
    // return s==a;

    size_t j = 0;
    for (size_t i = 0; i < size; i++)
    {
        if (Compare(array[i], a.array[j]) == 0)
        {
            j++;
        }
    }
    return j == a.size;
}

bool DynamicArray::ContnsContains(const DynamicArray &a)
{
    // 滑动窗口
    for (int i = 0; i <= size - a.size; i++)
    {
        DynamicArray b;
        b = Subsquence(i, a.size);
        b.SetCompareFunc(Compare);
        if (b == a)
            ;
        {
            return true;
        }
    }
    return false;
}

DynamicArray DynamicArray::Subsquence(size_t index, size_t len)
{
    DynamicArray result;
    if (index + len > size)
    {
        return result;
    }

    for (size_t i = index; i < index + len; i++)
    {
        result.InsertTail(array[i]);
    }
    return result;
}

void DynamicArray::ReSize(size_t capacity)
{
    this->capacity = capacity;
    this->size = size > capacity ? capacity : size;
    ElemetType *p = new ElemetType[capacity];
    for (size_t i = 0; i < size; i++)
    {
        p[i] = array[i];
    }
    delete[] array;
    array = p;
}

size_t DynamicArray::partition(size_t start, size_t end)
{
    size_t left = start;
    size_t right = end;
    ElemetType temp = array[start];
    while (left < right)
    {
        while (Compare(array[right], temp) > 0 && left < right)
        {
            right--;
        }
        if (left < right)
        {
            array[left] = array[right];
            left++;
        }

        while (Compare(array[left], temp) < 0 && left < right)
        {
            left++;
        }

        if (left < right)
        {
            array[right] = array[left];
            right--;
        }
    }
    array[left] = temp;
    return left;
}

void DynamicArray::InsertSort(size_t start, size_t end)
{
    for (size_t i = start + 1; i <= end; i++)
    {
        size_t j = i;
        ElemetType temp = array[i];
        for (; j > start; j--)
        {
            if (Compare(array[j - 1], temp) > 0)
            {
                array[j] = array[j - 1];
            }
            else
            {
                break;
            }
        }
        array[j] = temp;
    }
}

// 排序算法
void DynamicArray::FastSort(size_t start, size_t end, size_t CurDepth, int MaxDepth)
{
    if (start >= end)
    {
        return;
    }

    // 如果没有达到最大的递归深度
    if (CurDepth < MaxDepth)
    {
        // 对数列分组
        size_t par = partition(start, end);
        // size_t是无符号是当par=0时par-1为大数
        if (par != 0)
        {
            FastSort(start, par - 1, CurDepth + 1, MaxDepth);
        }
        FastSort(par + 1, end, CurDepth + 1, MaxDepth);
    }
    // 超过最大深度,可以使用如：插入排序
    else
    {
        InsertSort(start, end);
    }
}

void DynamicArray::show()
{
    for (size_t i = 0; i < size; i++)
    {
        Print(array[i]);
    }
    std::cout << std::endl;
}

}
